package cn.bellychang.wangzheng.string;

/**
 * @author ChangLiang
 * @date 2021/2/18
 */
public class BMSolution {

    private static final int SIZE = 256;

    private void generateBC(char[] b, int m, int[] bc){

        // 初始化bc
        for (int i = 0; i < SIZE; i++) {
            bc[i] = -1;
        }

        for (int i = 0; i < m; i++) {
            // 计算b[i]的ASCII值
            int ascii = (int) b[i];
            bc[ascii] = i;
        }
    }

    // 如何表示模式串中不同的后缀子串呢？
    // 因为后缀子串的最后一个字符的位置是固定的，下标为 m-1，我们只需要记录长度就可以了。通过长度，我们可以确定一个唯一的后缀子串。

    private void generateGS(char[] b, int m, int[] suffix, boolean[] prefix) {
        for (int i = 0; i < m; i++) {
            suffix[i] = -1;
            prefix[i] = false;
        }

        // 我们拿下标从 0 到 i 的子串（i 可以是 0 到 m-2）与整个模式串，求公共后缀子串

        // 如果公共后缀子串的长度是 k，那我们就记录 suffix[k]=j（j 表示公共后缀子串的起始下标）

        // 如果 j 等于 0，也就是说，公共后缀子串也是模式串的前缀子串，我们就记录 prefix[k]=true

        for (int i = 0; i < m-1; i++) {  // b[0,i]

            // j+1 表示公共后缀子串在b[0,i]中的起始下标
            int j = i;

            //  b[0,i]与b[0, m-1] 公共后缀子串长度
            int k = 0;

            while (j >= 0 && b[j] == b[m - 1 - k]) {
                // 与 b[0, m-1]求公共后缀子串
                --j;
                ++k;
                // j+1 表示公共后缀子串在b[0,i]中的起始下标
                suffix[k] = j+1;
            }
            if (j == -1) {
                // 如果公共后缀子串也是模式串的前缀子串
                prefix[k] = true;
            }
        }
    }

    public int bm(char[] a, int n, char[] b, int m) {
        // 记录模式串中每个字符最后出现的位置
        int[] bc = new int[SIZE];

        // 构建坏字符哈希表
        generateBC(b,m,bc);

        // suffix数组 下标表示后缀子串的长度
        // 下标对应的数组值存储的是，在模式串中跟好后缀{u}相匹配的子串{u*}的起始下标值
        int[] suffix = new int[m];

        // 记录模式串的后缀子串是否能匹配模式串的前缀子串
        boolean[] prefix = new boolean[m];

        generateGS(b, m, suffix, prefix);

        // i表示主串与模式串对齐的第一个字符
        int i = 0;

        while (i <= n - m) {
            int j;
            // 模式串从后往前匹配
            for (j = m - 1; j >=0; j--) {
                // 坏字符对应模式串的下标是j
                if (a[i + j] != b[j]) {
                    break;
                }
            }
            if (j < 0) {
                // 匹配成功 返回主串与模式串第一个匹配的字符的位置
                return i;
            }

            // 坏字符
            int x = j - bc[(int) a[i + j]];

            // 好后缀
            int y = 0;
            // 如果有好后缀的话
            if (y < m - 1) {
                y = moveByGS(j, m, suffix, prefix);
            }
            // 我们可以分别计算好后缀和坏字符往后滑动的位数，
            // 然后取两个数中最大的，作为模式串往后滑动的位数。
            // 这种处理方法还可以避免我们前面提到的，根据坏字符规则，计算得到的往后滑动的位数，有可能是负数的情况。
            i = i + Math.max(x, y);
        }
        return -1;
    }

    /**
     * 在模式串跟主串匹配的过程中，遇到不能匹配的字符时，如何根据好后缀规则，计算模式串往后滑动的位数？
     * @param j 表示坏字符对应的模式串中的字符下标
     * @param m 表示模式串长度
     * @param suffix
     * @param prefix
     * @return
     */
    private int moveByGS(int j, int m, int[] suffix, boolean[] prefix) {
        // 好后缀长度
        int k = m - 1 - j;
        if (suffix[k] != -1) {
            return j - suffix[k] + 1;
        }
        for (int r = j + 2; r <= m-1; r++) {
            // 好后缀的后缀子串 b[r, m-1]（其中，r 取值从 j+2 到 m-1）的长度 k=m-r，
            // 如果 prefix[k] 等于 true，表示长度为 k 的后缀子串，有可匹配的前缀子串，这样我们可以把模式串后移 r 位
            if (prefix[m - r] == true) {
                return r;
            }
        }
        // 如果两条规则都没有找到可以匹配好后缀及其后缀子串的子串，我们就将整个模式串后移 m 位
        return m;
    }
}
